2048 Without New Tiles is NP-Hard

Introduction

Background

2048 is a single-player puzzle game consisting of a 4x4 board. On this board are numbered tiles, whose values are base 2^k for k > 1.

Each turn, the player makes a move in a single direction (up, down, left, or right), which then slides all tiles on the board in that direction. Tiles slide along the board until they hit another tile or the end of the board. When a tile hits another tile of the same value, the two tiles merge into a single tile bearing the sum of their values. After each move, a 2 or 4 tile is randomly generated in an empty cell.

The goal of the game is to merge tiles until the player achieves the 2048 tile. If before then, however, the board fills and there are no more potential merges, then the player loses.

Our Problem

What we have described in the previous section is the original 2048 game. The original 2048 game has been proven to be NP-complete by a research paper that we will not be discussing but can be read here for further learning.

Instead, based on a research paper titled “2048 Without New Tiles is Still NP-Hard” by A. Abdelkader, A. Acharya, and P. Dasler, we will analyze a variant of the 2048 game. (All information used in this blog post references the content of this research paper.) In this variant, no new tiles are generated throughout the game. Instead, the board begins pre-configured with a specific arrangement of tiles. Additionally, the board is a rectangular grid of arbitrary size mxn, as opposed to 4x4.

We will address the following decision problem, 2048-TILE: “Given a configuration of tiles on an m x n board, is it possible to obtain a tile of value 2048?”

We will prove that 2048-TILE is NP-hard.

The Proof

We set out to prove that 2048-TILE is NP-hard. To do so, we prove that 2048-TILE can be reduced to something already known to be able to be solved in polynomial time. Here, we will reduce to 3SAT. Recall that 3SAT is the Boolean satisfiability problem, where we have a Boolean where three OR-statements are connected together as one AND-statement. We want to find a satisfiable set of variables to this Boolean so that it will evaluate to true.

Polynomial Time

Since we are proving that 2048 TILE is NP- hard, we want to show that 2048-TILE is in NP. Therefore, we need to show that 2048 TILE can be done in polynomial time. We will first bind the number of moves between two merges and then treat each move as a flip on the board. As a result, each tile will move at O(mn) (recalling the board has a size of (m x n)) length. Therefore, when two tiles merge, it will take at most O(m2n2) ((O(mn) x O(mn)). Since tiles move at most, O(m2n2) length, 2048-TILE can be done in polynomial time and is in NP.

The Reduction: 3SAT < 2048-TILE

We will now show the reduction from 3SAT to 2048-TILE. To do this, we need to transform 3SAT into a game of 2048-TILE. When we do this, our goal is to complete this transformed game in such a way that we arrive at a satisfiable assignment for 3SAT.

Reducing 3SAT to 2048-TILE

This is our transformation from 3SAT to 2048-TILE. Remember that in 2048-TILE, no new tiles are generated. We start off with a pre-configured board with a specific arrangement of tiles. Within this specific arrangement, we have a 2-4 lattice of tiles (in other words, an alternating pattern of 2- and 4-tiles) in which those tiles cannot merge, as well as merge-able tiles of higher, colored values that constitute our variables, clauses, and literals. These are concepts familiar to us from 3SAT, but here they take the form of tiles arranged in units called “gadgets.”

Our goal in using these gadgets is to move tiles around in a certain way, so that when one gadget’s tiles move, they cause the tiles of another gadget to move, creating a domino effect until we manage to get a true evaluation of the Boolean sequence.

We will now describe the gadgets used in order to piece together our understanding of the reduction.

Displacers

The most basic unit of our gadgets is the displacer. A displacer is a pair of 2x2 blocks, and it can either be inactive or active. In its inactive state, you can see that the tiles are misaligned, and a merge can’t be performed. In its active state, the tiles are aligned so that a merge can take place. In order to activate one displacer, we rely on the movement and merging of other displacers on the board to shift this middle block into place.

Variable Gadget

The next gadget is the variable gadget, each of which contains displacers. The variable gadgets come in pairs, one on either side of the board, and we have four variables, x0, x1, x2, x3, which correspond to the very same variables in our 3SAT Boolean. Just like the Booleans, our variable gadgets have truth values. They are assigned truth value based on the direction in which we slide the tiles when we activate a variable’s respective displacer. A slide to the right corresponds to true, and a slide to the left corresponds to false. When we merge one variable gadget, the movement of its tiles sets up to activate the next variable gadget, and so on.

Literals

Clauses

When we move around the tiles in our variable gadgets, the variable gadgets aren’t the only things on the board affected. As we slide left and right, the movements also affect the arrangement of the group of displacers in the middle of the board. These are our literals. If these literals get pushed and pulled by the variables in an optimal way, the vertical displacers inside will be activated, and a downward slide is made possible. In that case, when we slide downward, we are able to pull down the blocks at the top of the board. These blocks at the top are our clauses. When we pull a clause down, that is equivalent to satisfying a clause in our 3SAT Boolean.

Key-Lock Gadget

Now, our goal is to satisfy all the clauses of our 3SAT Boolean. We can confirm that we have produced a satisfiable assignment for 3SAT using the key-lock gadget in the upper right-hand corner of the board. You can see that at the beginning of the game this is an inactive displacer; we can’t merge the tiles. However, if we move our variables in an optimal way, allowing us to merge our literal displacers and therefore pull our clauses down, then our key-lock gadget displacer should activate, and we can merge its tiles. If and when we merge this displacer, then we have created a satisfiable assignment for 3SAT, completing the reduction.

Animated reduction

In the above animation, you can see the full reduction. Note the sliding of tiles and merging of the variable gadgets at the bottom of either side of the board. As that happens, there is simultaneous movement of literals in the middle of the board and occasionally the downward pull of a clause from the top. This sequence continues until the key-lock gadget also locks into place, completing the reduction.

Upon successfully completing the reduction, we have proved that 3SAT indeed reduces to 2048-TILE, thereby proving that 2048-TILE is NP-hard.

Discussion

Assessment

Overall the research paper explained the proof in a very organized manner. The authors explained all the definitions used in the proof and laid out clearly what they set out to show. In addition, this research paper provided diagrams to illustrate where the gadgets were and their role in the reduction. To further our understanding, an animation was provided to help guide us with the reduction. It was useful to see by ourselves how each move impacted the reduction and the types of moves we had to make to get there.

Connecting the Results

Using reduction, we found out that 2048-TILE is NP hard. We found out that the reduction acted similarly to a domino effect. By having one active gadget and then reducing it, all the once inactive gadgets became active. This action then triggered the clause gadget (which is what we want) and the key- lock gadget (which verifies that we got to the 2048-TILE).

This connects to the real world because knowing that 2048 is NP hard helps programmers develop new levels and variations of the game (similar to the game we studied in our proof). We now know it is possible to get to the 2048 tile and even go beyond to the 4096 tile if people move the tiles correctly. Also little did we know, as we were playing 2048, we were all using computational theory.

Though we understood the gist of the proof, it was hard to understand some of it. This was because sometimes we could not understand the details of the proof or some of the definitions and how it impacted the reduction. It was easy to get lost in the details to understand the big picture of the proof. This research paper also tackled multiple topics besides proving 2048-TILE. Therefore to improve, they should just focus on the proof of 2048-TILE and choose a topic that is related to it to be more concise.

What was particularly helpful in understanding the reduction was the presence of images and diagrams. A supplemental resource was a website, found here, where you can perform the reduction yourself to see how all the pieces interact as you move the tiles. We encourage readers to try the reduction themselves, as well!

Member Contributions

Alexis Kilayko, like all members, read the research paper on which the project was based. She was the team member primarily in charge of studying and understanding the proof. She formatted the PowerPoint, collected the necessary images and created the reduction animation, as well as set up the blog post. In terms of the content of the blog post, she wrote the introductory and reduction sections. Once the blog post was complete she checked for errors.

Libby Leung, like all members, read the research paper on which the project was based. She was the team member primarily in charge of evaluating the significance and takeaways of the research paper, the quality of the proof, and the problem’s application to the world. She organized the content, order, and flow of the in-class oral presentation. In terms of the content of the blog post, she wrote the polynomial time and discussion sections.